package com.c2b.algorithm.leetcode.base;

import java.util.Arrays;

/**
 * <a href='https://leetcode.cn/problems/stone-game-vi/'>石子游戏 VI(Stone Game VI)</a>
 * <p>Alice 和 Bob 轮流玩一个游戏，Alice 先手。</p>
 * <p>一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。</p>
 * <p>给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。</p>
 * <p>所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。</p>
 * <p>
 * 请你推断游戏的结果，用如下的方式表示：
 *     <ul>
 *         <li>如果 Alice 赢，返回 1 。</li>
 *         <li>如果 Bob 赢，返回 -1 。</li>
 *         <li>如果游戏平局，返回 0 。</li>
 *     </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：aliceValues = [1,3], bobValues = [2,1]
 *      输出：1
 *      解释：
 *          如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
 *          Bob 只能选择石子 0 ，得到 2 分。
 *          Alice 获胜。
 *
 * 示例 2：
 *      输入：aliceValues = [1,2], bobValues = [3,1]
 *      输出：0
 *      解释：
 *          Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
 *          打平。
 *
 * 示例 3：
 *      输入：aliceValues = [2,4,3], bobValues = [1,6,7]
 *      输出：-1
 *      解释：
 *          不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
 *          比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
 *          Bob 会获胜。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>n == aliceValues.length == bobValues.length</li>
 *         <li>1 <= n <= 10^5</li>
 *         <li>1 <= aliceValues[i], bobValues[i] <= 100</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/2/29 14:05
 */
public class LC1686Stone_Game_VI_M {

    static class Solution {
        /*
                每一步应尽可能的选择能拉开分值最大的石头
                证明：假设有两个石头i和j，价值分别是 ai, bi 和 aj, bj
                    若 Alice选择 i，而Bob选择 j；则分数差为 ai-bj
                    若 Alice选择 j，而Bob选择 i；则分数差为 aj-bi

                    对于Alice来说，选择哪一种，取决于分数差的差：(ai-bj)-(aj-bi)=(ai+bi)-(aj+bj)。
                    当这个值>0时，Alice会优先选择 i ，当这个值<0，Alice会优先选择 j。
                    因此，Alice选择时，会优先选择(ai+bi)大的石头。同理，Bob选择时，也会优先选择(ai+bi)大的石头
         */
        public int stoneGameVI(int[] aliceValues, int[] bobValues) {
            int n = aliceValues.length;
            int[][] arr = new int[n][3];
            for (int i = 0; i < n; i++) {
                arr[i][0] = aliceValues[i] + bobValues[i];
                arr[i][1] = aliceValues[i];
                arr[i][2] = bobValues[i];

            }
            Arrays.sort(arr, (a, b) -> b[0] - a[0]);
            // 两个人的分数差
            int scoreDiff = 0;
            for (int i = 0; i < n; i++) {
                scoreDiff += i % 2 == 0 ? arr[i][1] : -arr[i][2];
            }
            return Integer.compare(scoreDiff, 0);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.stoneGameVI(new int[]{1, 3}, new int[]{2, 1}));
        System.out.println(solution.stoneGameVI(new int[]{1, 2}, new int[]{3, 1}));
    }
}
